#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
using ll = long long;
int T;
ll a, m;
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}
ll phi(ll x)
{
    ll res = x;
    for (int i = 2; i <= x / i; i++)
    {
        if (x % i == 0)
        {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) res = res / x * (x - 1);
    return res;
}
int main()
{
    cin >> T;
    while (T--)
    {
        cin >> a >> m;
        ll d = gcd(a, m);
        cout << phi(m / d) << endl;
    }
    return 0;
}